package Hot_100;

/*

    题目: 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n
         互不相同的 二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

    思路: 动态规划

        设含n个结点的二叉树个数为G(n)
        f(n)表示以“序号n” 为根结点的二叉树个数
        则可以得到如下的递推式: 
        1)  f(i)=G(i-1)*G(n-i)           [本题的前提是二叉搜索树，所以左子树结点个数必须严格为 i-1]
        2)  G(n)=f(1)+f(2)+f(3)+...+f(n)

        结合1、2可得:
            G(n)=G(0)*G(n-1) + G(1)*G(n-2) + G(2)*G(n-3) + ... + G(n-1)*G(0)

        如果是普通二叉树:
        选中其中一个结点为根结点，
            0个结点构成的二叉树个数为1   G(0)=f(0)
            1个结点构成的二叉树个数为1   G(1)=f(1)
            2个结点构成的二叉树的个数为  G(2)=f(0)*f(1)+f(1)*f(0)   即左子树有一个结点，右子树没有结点 + 左子树没有结点，右子树有一个结点
            3个结点构成的二叉树个数为    G(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)
            ...
            n个结点构成的二叉树个数为    G(n)=f(0)*f(n-1) +f(1)*f(n-2) + ... + f(n-1)*f(0)
            所以得到的二叉树个数和二叉搜索树的个数是一样的
* */
public class T96_numTrees {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;  //G(0)
        dp[1] = 1;  //G(1)

        for (int i = 2; i <= n; i++) { //G(2) ~ G(n)
            for (int j = 0; j <= i - 1; j++) {
                // 从递推式 (G(n)=G(0)*G(n-1) + G(1)*G(n-2) + G(2)*G(n-3) + ... + G(n-1)*G(0))的第一项可知 0 <= j <= n-1
                dp[i] += dp[j] * dp[i - (j + 1)];
            }
        }

        return dp[n];
    }
}